/*
 * @Author: szx
 * @Date: 2022-02-16 12:22:57
 * @LastEditTime: 2022-02-16 13:00:27
 * @Description:
 * @FilePath: \leetcode\1900-1999\1996\1996.js
 */
/**
 * @param {number[][]} properties
 * @return {number}
 */

// 超时
var numberOfWeakCharacters = function (properties) {
    let res = 0;
    const n = properties.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (properties[i][0] < properties[j][0] && properties[i][1] < properties[j][1]) {
                res++;
            }
        }
    }
    return res;
};

// var numberOfWeakCharacters = function (properties) {
//     let res = 0;
//     const n = properties.length;
//     properties.sort((a, b) => {
//         return a[0] == b[0] ? a[1] - b[1] : b[0] - a[0];
//     });
//     console.log(properties);
//     let maxRight;
//     for (let p of properties) {
//         if (p[1] < maxRight) res++;
//         else {
//             maxRight = p[1];
//         }
//     }
//     return res;
// };

var numberOfWeakCharacters = function (properties) {
    let res = 0;
    properties.sort((a, b) => {
        return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
    });
    const st = [];
    for (const p of properties) {
        while (st.length && st[st.length - 1] < p[1]) {
            st.pop();
            res++;
        }
        st.push(p[1]);
    }
    return res;
};

console.log(
    numberOfWeakCharacters([[7,7],[1,2],[9,7],[7,3],[3,10],[9,8],[8,10],[4,3],[1,5],[1,5]])
);
